methods_num = 0
m = int(input('请输入传教士/野人数目：'))
n = int(input('请输入船上人数上限：'))
status_list = []


class Status:
    def __init__(self, ml, cl, bl):
        self.ml = ml
        self.cl = cl
        self.bl = bl


def legal(status):
    if len(status_list):
        for every in status_list:
            if status.ml == every.ml and status.cl == every.cl and status.bl == every.bl:
                return False
        if status.ml != 0 and status.ml < status.cl:
            return False
        if m - status.ml != 0 and m - status.ml < m - status.cl:
            return False
    return True


def bfs(status):
    if status.ml == 0 and status.cl == 0 and status.bl == 0:
        for i in status_list:
            print('左岸修道士：' + str(i.ml), '左岸野人：' + str(i.cl), '左岸->右岸' if i.bl == 1 else '右岸->左岸')
            print('-----------------------------------')
        print('\n===================================\n')
        global methods_num
        methods_num += 1
        return
    if status.bl == 1:
        m_max = min(n, status.ml)
        c_max = min(n, status.cl)
    else:
        m_max = min(n, m - status.ml)
        c_max = min(n, m - status.cl)
    i = 0
    while i <= m_max:
        j = 0
        while j <= min(c_max, n - i):
            if i != 0 or j != 0:
                if status.bl == 1:
                    b_next = 0
                    ml_next = status.ml - i
                    cl_next = status.cl - j
                    s_next = Status(ml_next, cl_next, b_next)
                    if legal(s_next):
                        status_list.append(s_next)
                        bfs(s_next)
                        status_list.remove(s_next)
                else:
                    b_next = 1
                    ml_next = status.ml + i
                    cl_next = status.cl + j
                    s_next = Status(ml_next, cl_next, b_next)
                    if legal(s_next):
                        status_list.append(s_next)
                        bfs(s_next)
                        status_list.remove(s_next)
            j += 1
        i += 1


if __name__ == '__main__':
    s = Status(m, m, 1)
    status_list.append(s)
    bfs(s)
    print('可行路径数：', methods_num)
